/**
 * 207. 课程表
 * https://leetcode-cn.com/problems/course-schedule/
 */

/**
 * @param {number} course
 * @param {boolean[]} finishes
 * @param {number[][]} dependencies
 * @param {boolean[]} todolist
 * @return {boolean}
 */
function todo(course, finishes, dependencies, todolist) {
  if (finishes[course]) return true;
  const conditions = dependencies[course];
  if (!conditions.length) {
    finishes[course] = true;
    return true;
  }
  if (todolist[course]) {
    return false;
  }
  todolist[course] = true;
  for (let i = 0; i < conditions.length; i += 1) {
    if (!todo(conditions[i], finishes, dependencies, todolist)) {
      return false;
    }
  }
  finishes[course] = true;
  todolist[course] = false;
  return true;
}

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
function canFinish(numCourses, prerequisites) {
  const dependencies = new Array(numCourses);
  for (let i = 0; i < numCourses; i += 1) {
    dependencies[i] = [];
  }
  for (let i = 0; i < prerequisites.length; i += 1) {
    const [course, depend] = prerequisites[i];
    dependencies[course].push(depend);
  }
  const finishes = new Array(numCourses).fill(false);
  const todolist = new Array(numCourses).fill(false);
  for (let i = 0; i < numCourses; i += 1) {
    if (!todo(i, finishes, dependencies, todolist)) {
      return false;
    }
  }
  return true;
}

console.log(canFinish(2, [[1, 0]]) === true);
console.log(canFinish(2, [[1, 0], [0, 1]]) === false);
console.log(canFinish(20, [[0, 10], [3, 18], [5, 5], [6, 11], [11, 14], [13, 1], [15, 1], [17, 4]]) === false);
console.log(canFinish(5, [[1, 4], [2, 4], [3, 1], [3, 2]]) === true);
